/* The algorithm can be found on page 71.
   Divide and Conquer can be used to solve this problem.

Note: int -2147483648 ~ +2147483647 (4 Bytes)
*/

#include <iostream>
using namespace std;

int A[16]={13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7};
const int minInt = -2147483648;


// This tuple is used to record {left_index, right_index, sum}
struct tuple
{
	int left_index;
	int right_index;
	int sum;
};

tuple find_max_crossing_subarray(int *A, int low, int mid, int high)
{
	int left_sum = minInt;
	int sum = 0;
	int i=0;
	int left_max;
// Judge left part
	for(i=mid;i>low;i--)
	{
		sum+=A[i];
		if(sum>left_sum)
		{
			left_sum = sum;
			left_max = i;
		}
	}
	sum = 0;
	int right_sum = minInt;
	int right_max;
	int j=0;
// Judge right part
	for(j=mid+1;j<high;j++)
	{
		sum+=A[j];
		if(sum>right_sum)
		{
			right_sum = sum;
			right_max = i;
		}
	}
	tuple tmp;
	tmp.left_index = left_max;
	tmp.right_index = right_max;
	tmp.sum = left_sum+right_sum;
	return tmp;
}

tuple find_max_subarray(int *A, int low, int high)
{
	if(low==high)
	{
		tuple tmp;
		tmp.left_index = low;
		tmp.right_index = high;
		tmp.sum = A[low];
		return tmp;
	}
	else
	{
		int mid = (low+high)/2;
		tuple left = find_max_subarray(A,low,mid);
		tuple right = find_max_subarray(A,mid+1,high);
		tuple cross = find_max_crossing_subarray(A,low,mid,high);
		if((left.sum>right.sum) && (left.sum>cross.sum))
			return left;
		else if((right.sum>left.sum) && (right.sum>cross.sum))
			return right;
		else 
			return cross;
	}
}

int main()
{
	tuple tmp;
	tmp = find_max_subarray(A,0,15);
	cout << tmp.sum << endl;
	return 0;
}
